package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/problems/redundant-connection/
 * @author: STU756
 * @create: 2020-08-24 14:08
 */
public class Pro0684 {
    private int find(int[] parent, int x) {

        while(parent[x] != x) {
            x = parent[x];
        }
        return x;
    }

    private void union(int[] parent, int x, int y) {
        int parentx = find(parent, x);
        int parenty = find(parent, y);
        if(parentx != parenty) {
            parent[parentx] = parenty;
        }
    }

    //并查集
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n+1];
        for(int i = 0; i <= n; i++) {
            parent[i] = i;
        }
        for(int[] edge : edges ) {
            if(find(parent, edge[0]) == find(parent, edge[1])) {
                return edge;
            }else {
                union(parent, edge[0], edge[1]);
            }
        }
        return new int[0];
    }
}
